//#include <iostream>
//#include <string>
//#include <algorithm>
//#include <vector>
//#include <string>
//using namespace std;
//
//class Trie {
//
//private:
//	bool isEnd;
//	Trie* next[26];
//
//public:
//	/** Initialize your data structure here. */
//	Trie() {
//		isEnd = false;
//		memset(next, 0, sizeof(next));
//	}
//
//	/** Inserts a word into the trie. */
//	void insert(string word) {
//		Trie* node = this;
//		for (char w : word)
//		{
//			if (node->next[w - 'a'] == NULL)
//			{
//				node->next[w - 'a'] = new Trie();
//			}
//			node = node->next[w - 'a'];
//		}
//		node->isEnd = true;
//	}
//
//	/** Returns if the word is in the trie. */
//	bool search(string word) {
//		Trie* node = this;
//		for (char w : word)
//		{
//			node = node->next[w - 'a'];
//			if (node == NULL)
//			{
//				return false;
//			}
//		}
//		return node->isEnd;
//	}
//
//	/** Returns if there is any word in the trie that starts with the given prefix. */
//	bool startsWith(string prefix) {
//		Trie* node = this;
//		for (char w : prefix)
//		{
//			node = node->next[w - 'a'];
//			if (node == NULL)
//			{
//				return false;
//			}
//		}
//		return true;
//	}
//};
//
//int main()
//{
//	string word = "hello";
//	Trie *obj = new Trie();
//	obj->insert(word);
//	bool param_2 = obj->search(word);
//	bool param_3 = obj->startsWith("he");
//
//	system("pause");
//	return 0;
//}